
\chapter{Implementation}


\section{Implementation Environment}

The solution is implemented on a Ubuntu 7.10 Gutsy Gibbon Linux System. The hypervisor used is 3.1 Xen hypervisor for i386 architecture with non PAE. XenAccess version 0.4 was used for the implementation, this supports only Xen 3.0 and Xen 3.1 on 32bit systems. 
The Dom0 uses 2.6.20-100-generic kernel provided by Cedric Schieli. The vulnerable DomU uses a 2.6.18-xenU kernel compiled locally to support 32bit non-pae hypervisor.

The kernel binary images, ram disk files and the System.out files for every kernel that can be booted on Xen is stored in the Dom0 file system. Dom0 is the host that manages other DomUs, therefore all the necessary files and configurations should be accessible to the Dom0. When the system boots, Xen hypervisor is first loaded and on top of Xen, the Dom0 gets booted up. DomU host can be created by using a kernel binary image modified to be run on Xen that is compatible with the hypervisor. In addition the host requires a file system, for this a file system image is provided as a virtual block device(VBD). The kernel binary image, VBD image file and configuration files residing on the Dom0 are used to boot a new DomU. Other management of domains such as pause, unpause, destroy, reboot, shutdown, save, restore and migrate are performed from Dom0.

\subsection{Xen Security Considerations}

When deploying a Xen system, one must be sure to secure the management domain(Dom0) as much as possible. If the management domain is compromised, all other domains are also vulnerable. The following are a set of best practices used for Domain-0 \cite{xenUser}.

\begin{enumerate}

\item Run the smallest number of necessary services. The less things that are present in a management partition, the better. A service running as root in the management domain has full access to all other domains on the system.

\item A firewall with default-reject rules to restrict traffic to management domain will help prevent attacks on the management domain.

\item Do not allow users to access Domain-0 even as a unprivileged user.

\end{enumerate}  

The above best practices are used to keep the Dom0 secure so that the integrity detector is secure. In addition it should be mentioned that when accessing a network with many hosts, finding the Dom0 with the integrity detector will be too much work and discovering that such a detector exists on the hosts will be hard practically.


\section{XenAccess Implementation}

XenAccess is an open source library to help the mapping of virtualized memory between virtual hosts. This project is built on top of XenAccess. XenAccess has implemented the underlying difficult functionality of memory mapping. The main functionality provided by XenAccess is the translation of memory addresses needed to map the memory. After the required address is found, the mapping of that address to another host is provided by Xen control library ( XenCtrl). 

Translation of addresses on Xen virtualization is the initial step in implementing inter-VM memory accessing systems on Xen. Next is a look at the implantation of XenAccess to walkthrough how XenAccess performs the address translation and maps the memory as required. Some of the important codes will be discussed below.


\subsection{Initialization of a XenAccess instance}

\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
%\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=XenAccess Library  initialization functions ,label=lst:xenaccessLibInit]{}

#include <xenaccess/xenaccess.h>

	
    xa_instance_t xai;	/* holds the relevant information for a XenAccess instance */
        
    uint32_t dom ;	/* the domain ID of the host being looked into */

    /* initialize the xen access library */
    if (xa_init(dom, &xai) == XA_FAILURE){
        perror("failed to init XenAccess library");
        goto error_exit;
    }
    
	error_exit:
    
    /* cleanup any memory associated with the XenAccess instance */
    xa_destroy(&xai);




        \end{lstlisting}
    \end{minipage}
\end{center}

Using XenAccess library requires the initialization of the library as shown in listing \ref{lst:xenaccessLibInit}. 

\emph{xa\_instance\_t} holds the information about the XenAccess instance. This instance is populated with the information by the \emph{xa\_init()} procedure.

The XenAccess instance should be de-allocated using \emph{xa\_destroy()} procedure.


\subsection{Mapping the Global Page Directory}
Memory management translates Addresses using page tables. Global page directory is the first page accessed in the page table walkthrough. This address is stored in \emph{cr3} register to start the address translation. Figure \ref{fig:paging} shows how cr3 is used as the starting address for page table lookups.



\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=XenAccess Library  xa\_init() procedure. Code extracted from the XenAccess library source code,label=lst:xainit]{}

int xa_init (uint32_t domain_id, xa_instance_t *instance)
{

	/* initialize the instance->xc_handle */

 	//// call helper_init() 
	
	/* initializes the Domain info using XenCtrl  */
	/* initializes the Xen version  */
	/* read the xenaccess.conf file and initializes config info  *
	/* Determine page information; if pagin enabled, if PAE or non-PAE, if PSE  */
	
	/* initializes page_offset value;*/
	instance->page_offset = 0xc0000000;

	/* assume 4k pages for now, update when 4M page is found */
    	instance->page_shift = 12;
	instance->page_size = 1 << instance->page_shift;
	
	//// call linux_init()
	
	linux_system_map_symbol_to_address(instance, "swapper_pg_dir", &instance->kpgd); //gets the virtual address of the symbol from  System.map file
        instance->kpgd -= instance->page_offset;

	//call xa_read_long_phys(instance, instance->kpgd, &(instance->kpgd);	
	uint32_t paddr = instance->kpgd;

	unsigned char *memory = NULL;
	uint32_t offset = 0;
	memory = xa_access_physical_address(instance, paddr, &offset);

	*value = *((uint32_t*)(memory + offset));
        munmap(memory, instance->page_size);

	
}


        \end{lstlisting}
    \end{minipage}
\end{center}

Listing \ref{lst:xainit} shows some of the important code segments being executed when the xa\_init() procedure is called. The listing is the execution order when run in 32bit Linux with non-PAE for a host with no VT support (no HVM). Execution happens through multiple procedure calls, but shown under one procedure. Error paths have been ignored for simplicity of illustration. 

In the above listing lines 5 to 12 show inside comments the initializations that happen before the XenAccess instance can be used. Line 15 shows the page offset for Linux being set to 0xc0000000. 0xc0000000 is the virtual address of the start of the kernel addresses. This region belongs to the linearly mapped address space, making it possible to translate the addresses without using page tables.

Line 19 sets the size of a page table as 4096. 1 << 12 bitwise shift operator shifts the bits 12 positions to the left to create 10000000000(bin) which is equal to 4096.

Line 23 finds the virtual address of kernel symbol \emph{swapper\_page\_dir} from the System.map file of the hosts kernel. This address is the address of the \emph{global page directory} and stores it in \emph{instance->kpgd}.

Line 24 converts the virtual address of \emph{kpgd} to its physical address. Address translation is simple here as this falls in the linear-mapped addresses.

Line 31 calls the function xa\_access\_physical\_address(), the internals of this function will be discussed later. When this function is called, a reference to the frame ( equal to the size of page size ) of memory containing the required physical address is returned together with a offset into the page.

Line 33 the value of the reference pointer to \emph{page global directory} is obtained by referencing the frame accessing the memory location of the offset.

Now the starting reference needed for traversing the page tables has been found. Addresses which need to be translated using page tables can use this value to traverse the page tables.

\subsection{Mapping a physical address}
A known physical address of a different virtual machine can be mapped to the memory of the local virtual machine as described here. This goes into describe the function \emph{xa\_access\_physical\_address()} used in the earlier listing. 

\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=XenAccess Library  xa\_access\_physical\_address() procedure. Code extracted from the XenAccess library source code,label=lst:xaAccPhyAddr]{}

void *xa_access_physical_address ( xa_instance_t *instance, uint32_t phys_address, uint32_t *offset)
{
    unsigned long pfn;
    
    /* page frame number = physical address >> PAGE_SHIFT */
    pfn = phys_address >> instance->page_shift;
    
    /* get the offset */
    *offset = (instance->page_size-1) & phys_address;

    ////call xa_mmap_pfn(instance, PROT_READ, pfn);

    unsigned long mfn;

    mfn = helper_pfn_to_mfn(instance, pfn);

    unsigned char *memory = xc_map_foreign_range(instance->xc_handle, instance->domain_id, 1, PROT_READ, mfn);
    
    return memory;

}


        \end{lstlisting}
    \end{minipage}
\end{center}

Listing \ref{lst:xaAccPhyAddr} shows some of the code segments executed during this function call. In line 7 the \emph{page frame number} is calculated. Line 10 calculated the offset into the frame at which the given physical address reside.

Line 16 calls the function \emph{helper\_pfn\_to\_mfn()}, this returns the machine frame number of the given physical frame number. This function accesses the \emph{shared\_info\_frame} and obtains the \emph{pfn\_to\_mfn\_frame\_list} list. The machine frame number is obtained by traversing through the \emph{pfn\_to\_mfn\_frame\_list} list. Each one of the above mentioned frames are mapped to local memory and then accessed to obtain the values residing in them.

Line 18 calls \emph{xc\_map\_foreign\_range()} function of Xen Control Library to actually do the real mapping of the foreign memory to the local memory. The frame with the provided machine frame number is mapped and a pointer to the mapped frame is returned by the function.





\section{Implementation of the Integrity Monitor}

The integrity monitor is implemented as a user level application running on the DomU and it uses the library XenAccess to perform a major task of providing the memory needed. The programming language used to implement the integrity monitor is C. It has use C because the main library which is XenAccess is written in C and the low level memory accessing and usage of pointers can be done using C.

The current implementation has the ability to support the integrity checking of any static kernel table. The kernel tables needed to be checked for integrity are initialized in the defined type \emph{monitored\_kernel\_table} showed in listing \ref{lst:structKernelTable}. 

\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=Data type struct holding static kernel tables ,label=lst:structKernelTable]{}
typedef struct {
	char *name; //sys_call_table
	int table_size;
	void **table;	
	unsigned char checksum_ori[16];
	unsigned char checksum_last[16];
	void **original_table;	
} monitored_kernel_table;


        \end{lstlisting}
    \end{minipage}
\end{center}


Each of the data values of the code in Listing \ref{lst:structKernelTable} are described here. 
\begin{itemize}
\item \emph{name} holds the kernel symbol name of the kernel object.
\item \emph{table\_size} is the size of the table. 
\item \emph{**table} points to the mapped kernel table, this points to the memory of the other VM. 
\item \emph{**original\_table} holds the initial kernel table. This can be used for changed location detection and for replacing the original reference. 
\item \emph{checksum\_ori} and \emph{checksum\_last} holds the initial original checksum and the last calculated checksum.
\end{itemize}










The single most successful location to monitor most number of kernel exploits is the System call table. The authors of the Copilot paper \cite{copilot} have correctly detected the presence of 12 real-world rootkits by scanning the system call table. Many of the exploits can be easily done by redirecting the system call pointers. The prototype implementation of this project also is implemented to detect any change been done to the system call table.

The location of \emph{sys\_call\_table} symbol on the vulnerable host is found using the \emph{System.map} file corresponding to its kernel. XenAccess helps to map the memory of the vulnerable VM to the Monitoring VM and provides a void pointer to it. The mapped memory can be accessed by the user-level integrity monitor just as if the mapped memory belongs to local VM's memory.

Listing \ref{lst:kernelTableInit} shows how the \emph{monitored\_kernel\_table} is initialized. 


\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=Initializing kernel table to check intergrity ,label=lst:kernelTableInit]{}
void init_kernel_table( xa_instance_t *xai, monitored_kernel_table *kerneltable , char *name , int size){

   unsigned char *memory = NULL;
   uint32_t offset;
   kerneltable->name = malloc(sizeof(char)*20);

   strcpy(kerneltable->name,name );	
   kerneltable->table_size = size;

   memory = xa_access_kernel_symbol(xai, kerneltable->name ,&offset);
   kerneltable->table = (unsigned long)(memory + offset);

   kerneltable->original_table = malloc( (sizeof(long) * kerneltable->table_size) );
   bzero(kerneltable->original_table, ( kerneltable->table_size * sizeof(long))  );	
   memcpy( kerneltable->original_table , kerneltable->table , kerneltable->table_size * sizeof(long));
	
   calc_kernel_table_checksum_original(kerneltable);
	
}


        \end{lstlisting}
    \end{minipage}
\end{center}

In the current implementation the parameter value \emph{*name} is always ``sys\_call\_table". In listing \ref{lst:kernelTableInit} 
\begin{itemize}
\item lines 7 and 8 initializes the \emph{kerneltable} using the parsed parameters.
\item line 10 uses XenAccess library to map memory location of vulnerable VM's ``sys\_call\_table" and gets a pointer and offset into the frame containing the required address.
\item line 11 initializes a pointer to the required kernel table. In this case points to the \emph{``sys\_call\_table"}.
\item lines 13,14 and 15 obtains memory space to hold the kernel table, cleans up the obtained memory space and then copies the original kernel table to be stored for future references.
\item line 17 calculates the checksum of the original kernel table and stores it in \emph{kerneltable} .

\end{itemize}


Next the implementation periodically checks the hashes for the kernel tables. If a change in hash occurs, the locations of the change are found by comparing the current kernel table with the original table. The changed positions are reported.


\subsection{Semantics Generation}

Semantics generation is one of the major issues to make introspection based intrusion detection possible. Ideally the semantics of any kernel object belonging to any kernel image should be obtainable. This is a area yet to be explored in this project. In the current implementation the semantics are provided by manually inspecting the source code of the kernel table and when coding, statically provide the data type. 

The source code of the DomU kernel in file \emph{linux-2.6.18-xen/arch/i386/kernel/syscall\_table.S} gives the code used to initialize the ``sys\_call\_table".

\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=linux-2.6.18-xen/arch/i386/kernel/syscall\_table.S ,label=lst:syscalltable]{}
ENTRY(sys_call_table)
	.long sys_restart_syscall	/* 0 - old "setup()" system call, used for restarting */
	.long sys_exit
	.long sys_fork
	.long sys_read
	.long sys_write
	.long sys_open		/* 5 */
	.long sys_close
	.long sys_waitpid
	.long sys_creat
	.long sys_link
	.long sys_unlink	/* 10 */
	.long sys_execve
	.long sys_chdir
	.long sys_time
	.long sys_mknod
	.long sys_chmod		/* 15 */
	\\......
	.long sys_tee			/* 315 */
	.long sys_vmsplice
	.long sys_move_pages

        \end{lstlisting}
    \end{minipage}
\end{center}

Listing \ref{lst:syscalltable} contains assembly code written in C. The list contains 317 entries and each entry is of type \emph{long} and contains a function pointer. This in memory would look like a array of function pointers of data type \emph{long}. This information is used when generating the system call table again.



\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=System call table accessed as an array ,label=lst:findChange]{}

void find_change_of_kernel_table(monitored_kernel_table *kernel_table){
int size = (int)(kernel_table->table_size);
int i;
for(i=0 ; i<size; i++){
   if(	memcmp( &(kernel_table->original_table[i]) , 
      &(kernel_table->table[i]) , 4 )!= 0){
      printf("\n%s[%d] has changed:original- %x , now- %x\n",
      kernel_table->name , i ,
      (unsigned long *)(kernel_table->original_table[i]) , 
      (unsigned long *)(kernel_table->table[i] )  );
      }			
   }
}
        \end{lstlisting}
    \end{minipage}
\end{center}


Listing \ref{lst:findChange} shows a procedure that accesses the kernel table as a \emph{long} array. In lines 6, 7, 10 and 11 the kernel table has been accessed as a array. This means that the memory location obtained has been cast to the real data type. It is also important to notice that at the time of mapping only a \emph{void} pointer was initialized to the variable that is here been accessed as a array.


%\subsection{Static Kernel Object Integrity Scanning}

%\subsection{Dynamic Kernel Object Scanning}

%\subsection{Attack Identification }


\section{RootKit Implementation}

The amount of rootkits that are available for the 2.6 kernel are very low or not publicly available. In the article \cite{norootkits} it has been mentioned about the  lack of rootkits. In that article itself they describe how to implement a rootkit which shows that rootkits are possible to be deployed on 2.6linux kernels.

Due to the lack of publicly available rootkits that run on the DomU ( 2.6.18 kernel), this project implements a small loadable kernel module that changes entries of the \emph{sys\_call\_table}.




\lstset{language=C}
%\lstset{backgroundcolor=listinggray}
%\lstset{backgroundcolor=\color{listinggray}}
%\lstset{linewidth=90mm}
%\lstset{frameround=tttt}
%\lstset{frameround=trbl}
%\lstset{labelstep=1}
\lstset{keywordstyle=\color{blue}\textbf}
%\lstset{moredelim=[is][\ttfamily]{|}{|}}
\lstset{basicstyle=\ttfamily \small \bfseries}
\lstset{commentstyle=\ttfamily}
\lstset{stringstyle=\bfseries}
\lstset{showstringspaces=false}
\lstset{numbers=left,numberstyle=\ttfamily \small}
\lstset{breaklines=true}
\begin{center}
    \begin{minipage}{14cm}
        %\begin{lstlisting}[frame=trBL,indent=10mm,caption=My MATLAB Code,label=lst:matlab,gobble=4]{}
        \begin{lstlisting}[frame=trbl,caption=Rootkit prototype code extract ,label=lst:rootkit]{}

long *sys_call_table;
sys_call_table = 3224200376; //0xc02d64b8 

int (*original_call)(struct pt_regs);

int edu_call(struct pt_regs regs)
{
  pid_t pid;  
  pid = (*original_call)(regs);    
  return pid;
}

//------------------------------------------

void swapin_sys_call(int sysNo){
	original_call = *(sys_call_table + sysNo);
	*(sys_call_table + sysNo ) = edu_call;
	printk( KERN_ALERT "[edu]   Intercepting sys_call_table[%d] from %x to %x \n" , sysNo , original_call, edu_call); 

}

void swapout_sys_call(int sysNo){
	printk( KERN_ALERT "[edu] Restoring sys_call_table[%d]\n" , sysNo); 
	  *(sys_call_table + sysNo ) = original_call;
}

        \end{lstlisting}
    \end{minipage}
\end{center}

Listing \ref{lst:rootkit} gives some code segments of the prototype rootkit. The implementation redirects the system call entry to a new function that calls the original system call. The implementation changes the pointer of \emph{``sys\_call\_table"} to a different location, and can restore the changed entries.

\begin{itemize}
\item line 3 initializes the sys\_call\_table location manually as discovering the sys\_call\_table in kernel 2.6 requires a few work.
\item line 16 is the procedure used to change system call entry number \emph{sysNo}, to a different pointer.
\item line 23 is the procedure that restores the system call entry to the original reference.

\end{itemize}







